/*
* leetcode 227. 基本计算器 II
*
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "3+2*2"
输出：7
* */
/*
* */
import java.util.*;
class Solution {
    public int calculate(String s) {
        Deque<Integer> stack=new ArrayDeque<>();
        char[] ch=s.toCharArray();
        int n=s.length(),i=0,result=0;
        char op='+';
        while(i<n){
            if(ch[i]==' '){
                i++;
            }else if(ch[i]<='9'&&ch[i]>='0'){
                int tmp=0;
                while(i<n&&ch[i]<='9'&&ch[i]>='0'){
                    tmp=tmp*10+(ch[i]-'0');
                    i++;
                }
                if(op=='+')stack.push(tmp);
                else if(op=='-')stack.push(-tmp);
                else if(op=='*')stack.push(stack.pop()*tmp);
                else stack.push(stack.pop()/tmp);
            }else{
                op=ch[i];
                i++;
            }
        }
        while(!stack.isEmpty()){
            result+=stack.pop();
        }
        return result;
    }
}